1. Field of the Invention
The present invention relates to secure storage and sharing of electronic information. More particularly, the present invention provides a system and method for generating public and private keys based on a unique attribute of an individual, without requiring management, storage, maintenance and tracking of the public and private keys or key certificates by a conventional third party certificate authority.
2. Background of the Invention
Oftentimes people need to send menages or other electronic data in a secure manner. Such security is generally provided through the use of encryption. That is, rather than transmit a message in its plain text form, an encrypted version of the message is sent. Conventional encryption schemes encrypt on the basis of a key. Without the proper key to decrypt the message, the recipient sees only an unintelligible or a garbled message, which cannot be easily read.
A wide variety of encryption schemes have been developed and employed throughout history. One popular modern scheme is known as public key encryption. In public key encryption, a public-private key pair is created. When the sender desires to send a secure message to a recipient, the sender encrypts the message with the recipient's public key. Upon receiving the message, the recipient decrypts it using the recipient's private key.
The use of the public-private key pair can also be used to authenticate messages. Authentication assures the recipient that the sender is actually the person who sent the message. To authenticate a message, the sender encrypts a short message, known as a digital signature using the sender's private key. When the recipient receives the digital signature, the recipient decrypts it using the sender's public key. Since only the public key corresponding to the sender's private key can successfully decrypt the message, the message is authentic, i.e., sent by the sender, if the decryption produces the original short message.
One common form of public key encryption used conventionally is the RSA algorithm, developed by Rivest, Shamir and Adelman in 1978. The algorithm is described in U.S. Pat. No. 4,405,829, which is hereby incorporated by reference in its entirety. Briefly, in the RSA algorithm the product of two large primes, p and q, is computed as:n=pq.   (1) “n” is called the modulus. A number e is chosen (less than n) which is relatively prime to the product of (p−1) and (q−1). Two quantities are relatively prime if they have no common factors except 1. Another number d is then found such that the quantity (de−1) is divisible by the product (p−1)(q−1). This is done by finding an integral value k (k=1, 2, 3, . . . ), such that:d=(k(p−1)(q−1)+1)/e   (2) has a remainder of zero (0).
The values e and d are called the public and private exponents respectively. The public key is the pair (n, e) and the private key is the pair (n, d). As explained below, the encryption algorithm requires computing the eth power of certain values. Due to the computational complexity of raising values to a power, e is often chosen to be 3. The factors p and q can be kept with the private key or destroyed. The security of RSA is premised on the assumption that factoring n into p and q is difficult, i.e., it would take an unreasonably long time to factor n into p and q.
To send a message, the sender encrypts the plain text message, m, to create a ciphertext (encrypted) message, c using the recipient's public key. For example, in RSA:c=memod n.   (3) The encrypted message c is sent to the recipient. To decrypt the message, i.e., recover the plain text message, m, from the ciphertext message, c, the recipient uses the private key (n, d). For example, in RSA:m=cdmod n.   (4) 
To authenticate a message, the sender sends the encrypted digital signature, based on a message, m as:s=mdmod n.   (5) The recipient then checks the authenticity of the message by calculating:m=semod n.   (6) If the result is the original message m, then the message received by the recipient is authentic.
To ensure security the private key must be kept secret. The public key, however, must be distributed to anyone the sender desires to send secure messages to or digitally authenticate messages for. A significant problem with public key encryption is the distribution, maintenance and tracking of the public keys.
To handle these tasks, a public key infrastructure was established. At the center of the public key infrastructure is a hierarchy of one or more certificate authorities. Generally, a certificate authority creates digitally signed public-private key pairs (i.e., certificates). The private key is sent by a certificate to the party making the request for the public-private key pair. The private key is generally sent by U.S. mail or by some other very secure delivery. The private key is generally sent on a certificate which ensures the private key's authenticity. The certificate authority stores the public key in a database. The public key database is maintained by the certificate authority.
A sender desiring to send a message in a secure fashion to a recipient requests the recipient's public key certificate from the recipient or the certificate authority. The recipient or the certificate authority sends the sender a certificate containing the recipient's public key. Conventionally, the certificate is sent electronically, for example, by email. Using the recipient's key, the sender encrypts the message. The sender then sends the encrypted message to the recipient. When the recipient receives the message, the recipient decrypts the message using the recipient's private key.
There are several significant problems associated with certificate authorities and the conventional public key infrastructure (PKI). One is that currently there are no standards or regulations governing certificate authorities. Thus, anyone can form a certificate authority. Consequently, the quality of the services offered by different certificate authorities can range from excellent to poor. Poor quality of service by a certificate authority is likely to result in a greater occurrence of security breaches due to the mishandling of public-private key pair information.
In addition, certificate authorities must track an ever-increasing volume of public-private key pairs that may be needed. As more and more data transmission are encrypted, more and more key pairs will have to be created, stored and tracked. If there is a problem with one of these keys, a new key pair will have to be generated, stored and tracked.
Large volumes of key management tasks could overwhelm a particular certificate authority resulting in security breaches or inability to handle the demand for public keys. This could prevent senders from being able to send messages securely, or prevent recipients from authenticating messages they receive. Another problem is that of distributing the keys and/or key certificates to those that need them. With many users, this task can become unmanageable.
Another problem with the conventional public key infrastructure is that public keys are generated randomly. Therefore, a trusted third party, often a certificate authority, must issue certificates to individuals, essentially binding a person's identity to a particular public key.
In addition, each person's public and private key (or certificate) is stored on a computer that is subject to destruction, theft or compromise. Further, the use of a certificate only guarantees station-to-station authentication. Current certificate technology does not guarantee that communication is occurring with the owner of the certificate. Thus, someone else can use the computer on which the certificate is stored, and carry on a secure communication with an unwitting other party.
In addition, parties that wish to communicate with a person must have prior knowledge of that person's public key. Currently, however, no public key directory exists to which a sender can refer to obtain an individual's public key. This restricts the free flow of secure communication. In addition, parties that wish to repeatedly communicate with a particular person or persons must maintain a directory of public keys associated with those individuals. Such directories are conventionally referred to as key rings. These public keys occasionally expire and/or require updating and maintenance.
Another problem is that the certificate authority must keep track of all certificates it issues so that it can recover from situations in which an issued certificate is compromised. This is a significant and cumbersome task which can become overwhelming as the demand for public-private key pairs increases. In conjunction with the magnitude of the tracking problem, the certificate authority must maintain a revocation list of revoked certificates. This list must be consulted before an individual uses a particular certificate to send a secure communication. Revocation lists maintained by the certificate authority work at odds with personally maintained key rings. That is, it is difficult for a person to know if a particular certificate has been revoked without checking the revocation list each time a secure communication is desired. Further, keeping the revocation list current becomes a daunting task as the user of public key encryption increases.
Given these problems with conventional certificate authorities, there is a need for a secure, reliable system for creating and distributing public-private key pairs in an efficient manner.